#include <stdlib.h>

#include "../Utils/Utils.h"
#include "../Utils/BasicTypes.h"
#include "../LocalStack/LocalStack.h"

#include "sparse_matrix.h"

sparse_matrix_lst* allocate_sparse_matrix_lst(int n)
{
	sparse_matrix_lst* ret;
	int l;
	
	START();
	
	ret = (sparse_matrix_lst*)NEW(sizeof(sparse_matrix_lst));
	ret->rows = (cell_t**)NEW(sizeof(cell_t*) * n);
	ret->cols = (cell_t**)NEW(sizeof(cell_t*) * n);
	ret->n = n;
	
	for (l = 0; l < n; l++)
		ret->rows[l] = NULL;
	for (l = 0; l < n; l++)
		ret->cols[l] = NULL;
	
	RETURN(ret);
}

void free_sparse_matrix_lst(void* m)
{
	sparse_matrix_lst* matrix = (sparse_matrix_lst*)m;
	
	cell_t* iter = NULL;
	int rowCounter = 0;
	
	if (matrix != NULL)
	{
		for (rowCounter = 0; rowCounter < matrix->n; rowCounter++)
		{
			if (matrix->rows[rowCounter] != NULL)
			{
				for (iter = matrix->rows[rowCounter]->row_next; iter != NULL; iter = iter->row_next)
				{
					free(matrix->rows[rowCounter]);
					matrix->rows[rowCounter] = iter;
				}
				free(matrix->rows[rowCounter]);
			}
		}
	}
	
	MemoryAssert(4, NULL, matrix->rows, matrix->cols, matrix);
}

void mult_sparse_list(const sparse_matrix_lst* A, const elem* vec, elem* result)
{
	int i, n = A->n;

	for (i = 0; i < n; i++)
	{	
		cell_t* itr = (A->rows)[i];
		result[i] = 0;
		while (itr != NULL)
		{
			result[i] += itr->value * vec[itr->colind];
			itr = itr->row_next;
		}
	}
}

elem* DegVector(const sparse_matrix_lst* matrix, elem* vector)
{
	int l;
	
	for (l = 0; l < matrix->n ; l++)
		vector[l] = SumRow(matrix, l);
	
	return vector;
}

elem SumRow(const sparse_matrix_lst* matrix, unsigned row)
{
	elem ret = 0;
	cell_t* iter = NULL;
	for (iter = matrix->rows[row]; iter != NULL; iter = iter->row_next)
		ret += iter->value;
	
	return ret;
}

cell_t* InitCell(int rowInd, int colInd, elem value)
{
  cell_t* ret = NULL;
  NAssert(MemoryAssert(1, ret = (cell_t*)malloc(sizeof(cell_t))));
  
  ret->row_next = NULL;
  ret->col_next = NULL;
  ret->rowind = rowInd;
  ret->colind = colInd;
  ret->value = value;
  
  return ret;
}

/*
 * Creates a new sub sparse_matrix whos vertices are the elements in group.
 * 
 */

sparse_matrix_lst* PartialMatrix (const sparse_matrix_lst* adjMatrix, const NumList* group)
{
	sparse_matrix_lst* ret;
	cell_t** lastInCols = NULL;
	cell_t* trgIter = NULL;
	cell_t* tempCell = NULL;
	cell_t* srcIter = NULL;
	unsigned i, j;
	const NumList* groupIterI = NULL;
	const NumList* groupIterJ = NULL;
	const unsigned size = group->size;
	
	NAssert(adjMatrix != NULL && group != NULL);
	NAssert(MemoryAssert(1, lastInCols = (cell_t**)malloc(sizeof(cell_t) * size)));
	
	if ((ret = allocate_sparse_matrix_lst(size)) == NULL)
	{
		free(lastInCols);
		return NULL;
	}
	
	ret->n = size;
	
	for (i = 0; i < size; i++)
		lastInCols[i] = NULL;
	
	for (groupIterI = group, i = 0; groupIterI->next != NULL; groupIterI = groupIterI->next, i++)
	{
		srcIter = adjMatrix->rows[groupIterI->value];
		trgIter = NULL;
		
		for (groupIterJ = group, j = 0; groupIterJ->next != NULL; groupIterJ = groupIterJ->next, j++)
		{
			
			while((srcIter != NULL) && (srcIter->colind < groupIterJ->value))
				srcIter = srcIter->row_next;

			if (srcIter == NULL)
				break;
			
			if (srcIter->colind == groupIterJ->value)
			{
				if ((tempCell = InitCell(i, j, srcIter->value)) == NULL)
				{
					free(lastInCols);
					free_sparse_matrix_lst(ret);
					return NULL;
				}
				
				if (trgIter == NULL)
					ret->rows[i] = tempCell;
				else
					trgIter->row_next = tempCell;
				
				
				if (lastInCols[j] == NULL)
					ret->cols[j] = tempCell;
				else
					lastInCols[j]->col_next = tempCell;

				lastInCols[j] = tempCell;
				trgIter = tempCell;
			}
		}
	}
	
	free(lastInCols);
	
	return ret;
}
